import java.util.Stack;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/16 9:23
 * @description:
 */
public class Solution85 {
    //是leetcode84的变体
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int maxArea = 0;
        //定义left[i][j]表示：在第i行中，从第j列向左连续的 '1' 的数量（包括j列本身）。
        int[][] left = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != '1') {
                    left[i][j] = j - 1 < 0 ? matrix[i][j] - '0' : left[i][j - 1] + 1;
                } else {
                    left[i][j] = 0;
                }
            }
        }
        //以每一行作为 “柱状图的底部”，向上累积高度，计算能形成的最大矩形：
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int minWidth = left[i][j];
                int area = minWidth;
                //必须从下往上找
                for (int k = i - 1; k >= 0; k--) {
                    minWidth = Math.min(minWidth, left[k][j]);
                    area = Math.max(area, minWidth * (i - k + 1));
                }
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }
    public int maximalRectangle2(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[] heights = new int[n];//记录当前行的柱状图高度
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            // 1. 更新当前行的高度：若当前是'1'则累加高度，否则重置为0
            for (int j = 0; j < n; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            // 2. 用单调栈计算当前高度数组对应的最大矩形面积
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            // 栈非空且当前高度小于栈顶高度时，弹出栈顶并计算面积
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];// 弹出栈顶高度
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;// 计算宽度
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution85 solution = new Solution85();
        System.out.println(solution.maximalRectangle2(new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        }));
    }
}
